Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 5
з дисципліни: “Програмування” на тему:
Структура даних „Бінарне дерево пошуку”
Варіант 6
1. Мета роботи
Навчитись працювати з структурою даних “Бінарне дерево пошуку ”.
2. Постановка задачі
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Побудувати два бінарних дерева пошуку. Визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї вершини.
3. Алгоритм розв’язання задачі
Ініціалізувати бінарне дерево пошуку№1
Вивести на екран рядок “Enter tree #1:”
Вивести на екран рядок “Enter int element (0 - finish):”
Ввести з клавіатури число x
Якщо x≠0, то додати x в бінарне дерево пошуку№1
Якщо x≠0, то перейти до пункту 3
Роздрукувати бінарне дерево пошуку№1
Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№1
Ініціалізувати бінарне дерево пошуку№2
Вивести на екран рядок “Enter tree #2:”
Вивести на екран рядок “Enter int element (0 - finish):”
Ввести з клавіатури число x
Якщо x≠0, то додати x в бінарне дерево пошуку№2
Якщо x≠0, то перейти до пункту 11
Роздрукувати бінарне дерево пошуку№2
Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№2
Якщо з бінарного дерева пошуку№1 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№2 або якщо з бінарного дерева пошуку№2 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№1, то вивести на екран рядок “Yes”, в іншому разі вивести на екран рядок “No”
4. Текст програми
#include <stdio.h>
#include "pBTREE.c"
void MakeCopyTree(binary_tree rootF,binary_tree * rootT);
void DestroyTree(binary_tree root);
int NumPeaks(binary_tree root, binary_tree knot){
int num=0;
if (knot)
{
if (WhoFather(root,knot)&&(WhoLeft(knot)||WhoRight(knot))) num++;
num+=NumPeaks(root,WhoLeft(knot));
num+=NumPeaks(root,WhoRight(knot));
};
return num;
}
int NumLeafs(binary_tree knot){
int num=0;
if (knot){
num+=NumLeafs(WhoLeft(knot));
num+=NumLeafs(WhoRight(knot));
if ((!WhoLeft(knot))&(!WhoRight(knot))) num++;
}
return num;
}
int NumElem(binary_tree knot){
int num=0;
if (knot){
num+=NumElem(WhoLeft(knot));
num++;
num+=NumElem(WhoRight(knot));
}
return num;
}
int GoSym(binary_tree knot){
int num=0;
if (knot){
num+=GoSym(WhoLeft(knot));
if (NumElem(knot)==2) num++;
num+=GoSym(WhoRight(knot));
}
return num;
}
int TreesEq(binary_tree root1,binary_tree root2){
if ((!root1)&&(!root2)) return 1;
if ((root1)&&(root2)){
if (root1->data!=root2->data) return 0;
if (!TreesEq(WhoLeft(root1),WhoLeft(root2))) return 0;
if (!TreesEq(WhoRight(root1),WhoRight(root2))) return 0;
return 1;
}
return 0;
}
int Test1(binary_tree root1,binary_tree root2,binary_tree knot){
int data1,ret;
binary_tree btt;
if (knot){
if (WhoFather(root1,knot)&&(WhoLeft(knot)||WhoRight(knot))){
MakeCopyTree(root1,&btt);
data1=knot->data;
DeleteSearchTree(&btt, data1);
ret=0;
if (TreesEq(btt,root2)) ret=1;
DestroyTree(btt);
if (ret) return 1;
}
if (Test1(root1,root2,WhoLeft(knot))) return 1;
if (Test1(root1,root2,WhoRight(knot))) return 1;
}
return 0;
}
void DestroyTree(binary_tree root){
if (root){
DestroyTree(WhoLeft(root));
DestroyTree(WhoRight(root));
free(root);
}
}
void MakeCopyTreeH(binary_tree rootF,binary_tree * rootT){
if (rootF){
*rootT=MakeNode(rootF->data);
MakeCopyTreeH(WhoLeft(rootF),&((*rootT)->leftson));
MakeCopyTreeH(WhoRight(rootF),&((*...
